package code.c02_list.dlinkList;


/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/25 20:57
 * @package code.c02_list.classwork.examples
 * @description 设有一个整数双链表L，每个结点中除有prior、data和next这3个成员外，
 * 还有一个访问频度成员freq，在链表被起用之前，其值均初始化为零，并且所有结点的data值不相同。
 * 每当进行LocateElem(L，x)运算时，令元素值为x的结点中freq成员的值加1，并调整表中结点的次序，
 * 使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。
 * <p>
 * 设计满足上述要求的LocateElem算法和完整的程序，并用相关数据进行测试
 */

public class Exam_2_19 {

    private static void swap(DLinkNode1<Integer> p, DLinkNode1<Integer> q) {
        int tmp = p.data;
        p.data = q.data;
        q.data = tmp;

        tmp = p.freq;
        p.freq = q.freq;
        q.freq = tmp;
    }

    public static boolean locateElem(DLinkListClass1<Integer> L, Integer x) {
        DLinkNode1<Integer> p, pre;
        p = L.dhead.next;
        while (p != null && !p.data.equals(x)) {
            p = p.next;
        }
        if (p == null) {
            return false;
        }

        p.freq++;
        pre = p.prior;
        while (pre != L.dhead && pre.freq < p.freq) {
            swap(pre, p);
            p = pre;
            pre = p.prior;
        }

        return true;
    }

    public static void find(DLinkListClass1<Integer> L, Integer x) {
        System.out.println("查找值为：" + x + "的链表");
        if (locateElem(L, x)) {
            System.out.println("查找成功：双链表L：" + L.toString());
        } else {
            System.out.println("查找失败");
        }
    }

    public static void main(String[] args) {
        Integer[] a = {1, 2, 3, 4, 5};
        DLinkListClass1<Integer> L = new DLinkListClass1<>();
        L.createListR(a);

        System.out.println("L :" + L.toString());

        find(L, 5);
        find(L, 1);
        find(L, 4);
        find(L, 5);
        find(L, 2);
        find(L, 4);
        find(L, 5);
    }
}

class DLinkNode1<E> {

    // 计数器
    int freq;
    // 节点元素值
    E data;
    //前驱节点指针
    DLinkNode1<E> prior;
    // 后继节点指针
    DLinkNode1<E> next;

    public DLinkNode1() {
        freq = 0;
        prior = null;
        next = null;
    }

    public DLinkNode1(E data) {
        this.freq = 0;
        this.data = data;
        prior = null;
        next = null;
    }
}

class DLinkListClass1<E> {
    // 存放头节点
    DLinkNode1<E> dhead;


    public DLinkListClass1() {
        // 创建头节点
        dhead = new DLinkNode1<E>();
        dhead.prior = null;
        dhead.next = null;
    }

    public void createListR(E[] a) {
        DLinkNode1<E> s, t;
        t = dhead;
        for (int i = 0; i < a.length; i++) {
            s = new DLinkNode1<>(a[i]);
            t.next = s;
            s.prior = t;
            t = s;
        }
        t.next = null;
    }

    public String toString() {
        StringBuilder ans = new StringBuilder();
        DLinkNode1<E> p = dhead.next;
        while (p != null) {
            ans.append(p.data).append(" ");
            p = p.next;
        }
        return ans.toString();
    }
}
